package wtx.leetcode;

import java.util.*;
import java.util.Random;


class Solution {
    final static int CODE_NUM = 26;
    public int numDecodings(String s) {
        if (s == null) {
            return 0;
        }
        final int N = s.length();
        if (N == 0) {
            return 0;
        }
        if (s.startsWith("0")) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        int[] array = new int[N];
        for (int i = 0; i < N; ++i) {
            array[i] = s.charAt(i) - '0';
        }
        return numDecodings(array, 0, N);
    }
    private int numDecodings(int[] array, int start, int end) {
        if (end - start == 0) {
            return 1;
        }
        if (end - start == 1) {
            if (array[start] > 0) {
                return 1;
            } else {
                return 0;
            }
        }
        if (end - start == 2) {
            // total 2 case
            int ret = 0;
            int c1 = array[start], c2 = array[start + 1], c3 = array[start]*10 + array[start+1];
            if (c1 > 0 && c2 > 0) {
                ++ret;
            }
            if (c3 >= 10 && c3 <= CODE_NUM) {
                ++ret;
            }
            return ret;
        }
        if (end - start == 3) {
            // total 3 case
            int ret = 0;
            int c1 = array[start], c2 = array[start + 1], c3 = array[start+2];
            if (c1 > 0 && c2 > 0 && c3 > 0) {
                ++ret;
            }
            c1 = c1*10 + c2;
            if (c3 > 0 && c1 <= CODE_NUM && c1 >= 10) {
                ++ret;
            }
            c2 = array[start];
            c1 = array[start+1] * 10 + array[start+2];
            if (c2 > 0 && c1 <= CODE_NUM && c1 >= 10) {
                ++ret;
            }
            return ret;
        }
        int mid = (start + end)/2;
        // 如果mid为0，则不应该在这里split
        if (array[mid] == 0) {
            int code = array[mid-1] * 10 + array[mid];
            if (code <= CODE_NUM && code >= 10) {
                return numDecodings(array, start, mid-1) * numDecodings(array, mid + 1, end);
            } else {
                return 0;
            }
        } else {
            int prod = numDecodings(array, start, mid) * numDecodings(array, mid, end);
            int code = array[mid-1] * 10 + array[mid];
            if (code <= CODE_NUM && code >= 10) {
                int prod2 = numDecodings(array, start, mid-1) * numDecodings(array, mid + 1, end);
                return prod + prod2;
            } else {
                return prod;
            }
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numDecodings(""));
    }
}
